// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 10：
// 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
//
//        示例 1：
//
//
//        输入：n = 4
//        输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//        解释：如上图所示，4 皇后问题存在两个不同的解法。
//        示例 2：
//
//        输入：n = 1
//        输出：[["Q"]]
//
//
//        提示：
//
//        1 <= n <= 9

// 解题思路：
// 使用 3 个 bool 数组去表示列，主对角线和斜对角线有没有皇后，有设置为 true, 默认设置为 false
// 如果没有皇后，放置皇后，修改 bool 数组对应的元素为 true
// 继续递归下一行
// 返回本层时回溯
// pos == n 时收集结果

import java.util.ArrayList;
import java.util.List;

public class SolveNQueens {
    List<List<String>> ret;
    char[][] board;
    boolean[] col;
    boolean[] diag1;
    boolean[] diag2;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        board = new char[n][n];
        col = new boolean[n];
        diag1 = new boolean[2 * n];
        diag2 = new boolean[2 * n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = '.';
            }
        }
        dfs(n, 0);
        return ret;
    }
    public void dfs(int n, int pos){
        if(pos == n){
            List<String> path = new ArrayList<>();
            for(int i = 0; i < n; i++){
                StringBuilder row = new StringBuilder();
                for(int j = 0; j < n; j++){
                    row.append(board[i][j]);
                }
                path.add(row.toString());
            }
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < n; i++){
            if(col[i] == false && diag1[i - pos + n] == false && diag2[pos + i] == false){
                board[pos][i] = 'Q';
                col[i] = true;
                diag1[i - pos + n] = true;
                diag2[pos + i] = true;
                dfs(n, pos + 1);
                board[pos][i] = '.';
                col[i] = false;
                diag1[i - pos + n] = false;
                diag2[pos + i] = false;
            }
        }
    }
}
